Reliably storing a data element at a resource is an important capability of an information system. A data element is defined to be an item of information. Examples of a data element include an alphanumeric character, a string, an integer, and a floating point number, and any combination thereof. A resource is an apparatus capable of storing a data element.
A resource typically has a finite amount of memory for storing data elements. When the memory of a resource is full, additional data elements cannot be stored at the resource. In this case, the capabilities of the resource can be substantially compromised, and certain data elements that the resource is supposed to store can be lost permanently.
One known system addresses this problem by making available to the first resource a second resource that has memory to spare. For example, a first resource whose memory is full, or about to be full, stores a data element at a second resource. This sharing of memory advantageously distributes the burden of storing data elements across resources.
In one embodiment of this known system, a first resource is connected to a second resource through a network. When the memory space at the first resource becomes limited, the first resource sends a first data element to the second resource through the network, where the first data element is stored. When the first resource later needs the first data element, it sends a request through the network to the second resource. In response, the second resource sends the first data element back to the first resource through the network.
In another embodiment of this known system, a first resource is connected directly to a second resource through an interface. For example, the first resource is a smart card coupled to a second resource, a laptop computer, through a PCMCIA interface. When the memory in the smart card becomes limited, the smart card sends a first data element to the computer through the interface to be stored at the computer. When the smart card needs the first data element again, the smart card sends a request to the computer, and the computer returns the first data element to the smart card.
Although this known system mitigates the problems associated with the limited amount of available memory at a first resource, this known system disadvantageously provides no assurance to the first resource that the data element returned by a second resource is the same as the data element sent earlier from the first resource to the second resource to be stored. In other words, this system provides no assurance to the first resource that the data element retrieved from storage at the second resource has not been modified in some way.
Indeed, it is possible that the data element returned from the second to the first resource may be different from the data element that was sent from the first to the secord resource to be stored. To reflect this possibility, the data element sent from the first resource to be stored on the second resource is called the "first data element." The data element received at the first resource ostensibly from the second resource and purported to be the first data element is called the "second data element. "
The second data element may not be the same as its corresponding first data element for any of several reasons. For example, the second data element may have been the same as the first data element when it was sent from the second resource to the first resource, but been modified in transit to the first resource. For example, noise may have been injected into the second data element, corrupting it. Alternatively, the second data element may have been modified at a way point (e.g., a router, proxy, etc.) between the second and first resources. On the other hand, the second data element may have been modified (either accidentally or purposefully) at the second resource. Likewise, the request from the first resource for the first data element can be intercepted by a third party, which can inject its own version of the first data element by sending it to the first resource in response to the request. The first resource can then unknowingly accept a false version of the first data element as it was provided by the third party.
If the second data element is not the same as the first data element, and if the first resource is unable to detect this condition, then disaster can result. For example, suppose the first resource is responsible for computing new account balances for a bank. When the memory of the first resource becomes limited, the first resource stores certain account balances and the interim results of certain calculations at a second resource, also owned by the bank. The first resource receives a second data element that is not the same as its corresponding first data element. For example, the first resource stores a bank balance of $46,325.00 (the first data element) at the second resource, which the first resource later asks for from the second resource. The second resource returns the value $35.93 (the second data element). Thus, the account balance now stored at the first resource is erroneous, and all subsequent calculations based upon that incorrect account balance will also be erroneous.
There are certain known techniques for protecting the integrity of data that is stored in a possibly untrusted memory resource. See Nancy M. Amato and Michael C. Loui, Checking Linked Data Structures, Proceedings of the 24th Annual International Symposium on Fault-Tolerant Computing (FTCS), 1994; and Manual Blum, William Evans, Peter Gemmell, Sampath Kannan and Moni Noar, Checking the Correctness of Memories, Algorithmica, 12(2/3, pages 225-244, 1994 (also available in the proceedings of FOCS (Foundations of Computer Science) '91). These techniques address the problem of verifying the correctness of a large memory of size n bits maintained by an all-powerful adversary P (i.e., P has unlimited computer power), subject to update requests originator V that has a limited amount of trusted memory. It has been shown that P can fool V with an incorrect memory whenever V has access to less than log(n) bits of trusted memory. The reference, Manual Blum, William Evans, Peter Gemmell, Sampath Kannan and Moni Noar, Checking the Correctness of Memories, Algorithmica, 12(2/3, pages 225-244, 1994 and FOCS '91 Proceedings, also describes implementations of stacks and queues along these lines. The stack implementation uses log(H) memory accesses for operations on a stack of height H.
For practical purposes, it is both unduly expensive and unnecessary to provide for protection against an all-powerful adversary P. It would be more practical to develop a technique that is effective if adversary P is less than all-powerful, but is faster (has more computing power) than the V. It would be further advantageous if, unlike the techniques shown in the prior art, an unlimited amount of data could be stored in untrusted memory in a trusted fashion while using a constant number of bits of trusted memory. Further, the prior art performs a number of memory store and retrieve operations that increases with the amount of data stored on the untrusted resource. A better, more economical system would need to perform only some reasonably-sized fixed number of operations for any amount of data stored in a queue on the untrusted resource, no matter how large.